#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<ctime>
#include"BinarySearchTree.h"
using namespace std;

ofstream fout("data.txt");


/**
 *  对数组进行BSTSorting
 */
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
{


    /**
     * 如果 mode =1 ,对数组进行打乱
     */
    if(_mode)  random_shuffle(_arr.begin(),_arr.end());
 
    
    /**
     *  测试BST排序时间
     */
    BinarySearchTree<Comparable> tree;
    clock_t start, finish;
    start = clock();
    for(int i=0; i < _arr.size(); i++)
      {
	tree.insert(_arr[i]);
      }
    finish = clock();


    
    if(_arr.size()>20)
      fout <<endl<<"BSTSorting 运行时间为:" << double(finish - start) / CLOCKS_PER_SEC <<"秒" << endl;

    if(_arr.size() <20)
      tree.printTree();  
};




/**
 *  五组测试数据
 */
void test1()
{
  vector<double> _arr;
  _arr.push_back(3);
  _arr.push_back(4);
  _arr.push_back(9);
  _arr.push_back(3);
  _arr.push_back(2);
  _arr.push_back(3);
  BSTSorting(_arr , 0);
};


void test2()
{
   vector<double> _arr;
   for(int i=0;i<1000;i++)
     {      
       _arr.push_back(i);
     }
   fout << "（1） 升序排列的1000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};

void test3()
{
  vector<double> _arr;
   for(int i=-500;i<500;i++)
     {      
       _arr.push_back(i);
     }
   random_shuffle(_arr.begin(),_arr.end());
   fout << "（2） 随机排列的1000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};


void test4()
{
  vector<double> _arr;
   for(int i=-5000;i<5000;i++)
     {      
       _arr.push_back(i);
     }
   random_shuffle(_arr.begin(),_arr.end());
   fout << "（3） 升序排列的10000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};



void test5()
{
  vector<double> _arr;
   for(int i=-5000;i<5000;i++)
     {      
       _arr.push_back(i);
     }
   random_shuffle(_arr.begin(),_arr.end());
   fout << "（4） 随机排列的10000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};





void test6()
{
   vector<double> _arr;
   for(int i=0;i<100000;i++)
     {      
       _arr.push_back(i);
     }
   fout << "（5） 升序排列的100000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};



void test7()
{
   vector<double> _arr;
   for(int i=-50000;i<50000;i++)
     {      
       _arr.push_back(i);
     }
   random_shuffle(_arr.begin(),_arr.end());
   fout << "（6） 随机排列的100000个数据" << endl;
   BSTSorting(_arr , 0);
   BSTSorting(_arr , 1);
   fout << " "<< endl;
};






int main()
{
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  test7();
  return 0;
}
